from functools import cache
from typing import List


# 方法一： 记忆化搜索
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        @cache
        def dfs(i, j):

            if i == m - 1 and j == n - 1 and obstacleGrid[i][j] == 0:
                return 1
            if i >= m or j >= n or obstacleGrid[i][j] == 1:
                return 0
            return dfs(i + 1, j) + dfs(i, j + 1)

        return dfs(0, 0)

# 方法二： 动态规划
from typing import List


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        # 初始化 DP 表
        dp = [[0] * n for _ in range(m)]

        # 起点
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0

        # 初始化第一列
        for i in range(1, m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = dp[i - 1][0]
            else:
                dp[i][0] = 0

        # 初始化第一行
        for j in range(1, n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = dp[0][j - 1]
            else:
                dp[0][j] = 0

        # 填充 DP 表
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                else:
                    dp[i][j] = 0

        return dp[m - 1][n - 1]